// #pragma once
// #include <iostream>
// #include <list>
// #include <string>
// #include <assert.h>
// using namespace std;

//练习测试代码，测试迭代器
// namespace bit
// {
//     template <class T>
//     struct ListNode
//     {
//         ListNode<T> *_prev;
//         ListNode<T> *_next;
//         T _data;

//         ListNode(const T& data = T()):_prev(nullptr),_next(nullptr),_data(data){}

//     };

//     template <class T,class Ref>
//     struct __list_iterator
//     {
//         typedef ListNode<T> node;
//         typedef __list_iterator<T,Ref> self;
//         node* _node;
//         __list_iterator(node* node):_node(node){}

//         self& operator++()
//         {
//             _node = _node->_next;
//             return *this;
//         }

//         Ref  operator*()
//         {
//             return _node->_data;
//         }

//         bool operator!=(self& s)
//         {
//             return _node != s._node;
//         }
//     };
    

//     template <class T>
//     class list
//     {
//     private:
//         typedef ListNode<T> node;
//     public:
//         typedef __list_iterator<T,T&> iterator;
//         typedef __list_iterator<T,const T&> const_iterator;
//         iterator begin()
//         {
//             return _head->_next;
//         }

//         iterator end()
//         {
//             return _head;
//         }

//         const_iterator begin() const
//         {
//             return _head->_next;
//         }

//         const_iterator end() const
//         {
//             return _head;
//         }

//         list()
//         {
//             _head = new node();
//             _head->_next = _head;
//             _head->_prev = _head;
//         }

//         void push_back(const T& val)
//         {
//             node* temp = new node(val);
//             node* tail = _head->_prev;

//             temp->_prev = tail;
//             tail->_next = temp;

//             _head->_prev = temp;
//             temp->_next = _head; 
//         }

//     private:
//         node* _head;
//     };


//     void print_list(const list<int> v1)
//     {
//         for(auto& e : v1)
//         {
//             cout << e << endl;
//         }
//     }

//     void test()
//     {
//         list<int> v1;
//         v1.push_back(1);
//         v1.push_back(2);
//         v1.push_back(3);
//         v1.push_back(4);
//         print_list(v1);
//         // for(auto e : v1)
//         // {
//         //     cout << e << endl;
//         // }
//     }
// }

#pragma once
#include <iostream>
#include <list>
#include <string>
#include <assert.h>
#include "reverse_iterator.hpp"
using namespace std;

namespace bit
{
    // List的节点类
    template<class T>
    struct ListNode
    {
        ListNode(const T& val = T()) : _val(val), _pPre(nullptr), _pNext(nullptr) {}
        ListNode<T>* _pPre;
        ListNode<T>* _pNext;
        T _val;
    };

    template<class T>
    class list;

    //List的迭代器类
    template<class T, class Ref, class Ptr>
    class ListIterator
    {
        friend list<T>;

        typedef ListNode<T>* PNode;
        typedef ListIterator<T, Ref, Ptr> Self;
    public:
        ListIterator(PNode node) :_pNode(node) {}
        ListIterator(const Self& l) { _pNode = l._pNode; }
        Ref operator*() { return _pNode->_val; }
        Ptr operator->() { return &(_pNode->_val); }
        Self& operator++()
        {
            _pNode = _pNode->_pNext;
            return *this;
        }

        Self operator++(int)
        {
            Self temp(*this);
            _pNode = _pNode->_pNext;
            return temp;
        }

        Self& operator--()
        {
            _pNode = _pNode->_pPre;
            return *this;
        }

        Self& operator--(int)
        {
            Self temp(*this);
            _pNode = _pNode->_pPre;
            return temp;
        }

        bool operator!=(const Self& l) { return _pNode != l._pNode; }
        bool operator==(const Self& l) { return _pNode == l._pNode; }
    private:
        PNode _pNode;
    };


    //list类
    template<class T>
    class list
    {
        typedef ListNode<T> Node;
        typedef ListNode<T>* PNode;
    public:
        typedef ListIterator<T, T&, T*> iterator;
        typedef ListIterator<T, const T&, const T*> const_iterator;
        typedef Reverse_iterator<iterator,T&,T*> reverse_iterator;
        typedef Reverse_iterator<const_iterator,const T&,const T*> const_reverse_iterator;
    public:
        ///////////////////////////////////////////////////////////////
        // List的构造
        list()
        {
            CreateHead();
        }
        list(int n, const T& value = T());
        template <class Iterator>
        list(Iterator first, Iterator last);
        list(const list<T>& l);
        list<T>& operator=(list<T> l);
        ~list();


        ///////////////////////////////////////////////////////////////
        // List Iterator
        iterator begin()
        {
            return _pHead->_pNext;
        }

        iterator end()
        {
            return _pHead;
        }

        const_iterator begin()const
        {
            return _pHead->_pNext;
        }

        const_iterator end()const
        {
            return _pHead;
        }

        reverse_iterator rbegin()
        {
            return reverse_iterator(end());
        }

        reverse_iterator rend()
        {
            return reverse_iterator(begin());
        }

        reverse_iterator rbegin() const
        {
            return reverse_iterator(end());
        }

        reverse_iterator rend() const
        {
            return reverse_iterator(begin());
        }

        ///////////////////////////////////////////////////////////////
        // List Capacity
        size_t size() const
        {
            size_t cnt = 0;
            PNode cur = _pHead->_pNext;
            while (cur != _pHead)
            {
                cnt++;
                cur = cur->_pNext;
            }
            return cnt;
        }

        bool empty() const
        {
            return _pHead->_pNext == _pHead;
        }


        ////////////////////////////////////////////////////////////
        // List Access
        T& front() { return _pHead->_pNext->_val;  }
        const T& front()const { return _pHead->_pNext->_val; }
        T& back() { return _pHead->_pPre->_val; }
        const T& back()const { return _pHead->_pPre->_val; }


        ////////////////////////////////////////////////////////////
        // List Modify
        void push_back(const T& val) { insert(end(), val); }
        void pop_back() { erase(--end()); }
        void push_front(const T& val) { insert(begin(), val); }
        void pop_front() { erase(begin()); }
        // 在pos位置前插入值为val的节点
        iterator insert(iterator pos, const T& val);
        // 删除pos位置的节点，返回该节点的下一个位置
        iterator erase(iterator pos);
        void clear();
        void swap(list<T>& l);
    private:
        void CreateHead()
        {
            _pHead = new Node();
            _pHead->_pNext = _pHead;
            _pHead->_pPre = _pHead;
        }
    private:
        PNode _pHead;
    };

    template<class T>
    list<T>::list(int n, const T& value)
    {
        CreateHead();
        for (int i = 0; i < n; i++)
        {
            push_back(value);
        }
    }

    template<class T>
    template <class Iterator>
    list<T>::list(Iterator first, Iterator last)
    {
        CreateHead();
        while (first != last)
        {
            push_back(*first);
            ++first;
        }
    }

    template<class T>
    list<T>::list(const list<T>& l)
    {
        CreateHead();
        for (auto& e : l)
        {
            push_back(e);
        }
    }

    template<class T>
    list<T>& list<T>::operator=(list<T> l)
    {
        clear();
        swap(l);
        return *this;
    }

    template<class T>
    list<T>::~list()
    {
        clear();
        delete _pHead;
        _pHead = nullptr;
    }

    template<class T>
    ListIterator<T, T&, T*> list<T>::insert(iterator pos, const T& val)
    {
        PNode newnode = new Node(val);
        PNode Self = pos._pNode;
        PNode prev = pos._pNode->_pPre;
        
        prev->_pNext = newnode;
        newnode->_pPre = prev;
        newnode->_pNext = Self;
        Self->_pPre = newnode;
        
        return newnode;
    }

    template<class T>
    ListIterator<T, T&, T*> list<T>::erase(iterator pos)
    {
        assert(pos != end());
        PNode del = pos._pNode;
        PNode next = pos._pNode->_pNext;
        PNode prev = pos._pNode->_pPre;

        next->_pPre = prev;
        prev->_pNext = next;

        delete del;
        return next;
    }

    template<class T>
    void list<T>::clear()
    {
        PNode cur = _pHead->_pNext;
        while (cur != _pHead)
        {
            PNode next = cur->_pNext;
            erase(cur);
            cur = next;
        }
    }

    template<class T>
    void list<T>::swap(list<T>& l)
    {
        std::swap(_pHead, l._pHead);
    }



};


